Lucas' theorem

For the theorem in complex analysis, see Gauss–Lucas theorem.

In number theory, the Lucas' theorem expresses the remainder of division of the binomial coefficient \binom{m}{n} by a prime number p in terms of the base p expansions of the integers m and n.

Lucas' theorem first appeared in 1878 in papers by Édouard Lucas.[1]

Contents

Formulation

For non-negative integers m and n and a prime p, the following congruence relation holds:

\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,

where

m=m_kp^k%2Bm_{k-1}p^{k-1}%2B\cdots %2Bm_1p%2Bm_0,

and

n=n_kp^k%2Bn_{k-1}p^{k-1}%2B\cdots %2Bn_1p%2Bn_0

are the base p expansions of m and n respectively.

Consequence

Proof

There are several ways to prove Lucas' theorem; here is a combinatorial argument. Let M be a set with m elements, and divide it into mi cycles of length pi for the various values of i. Then each of these cycles can be rotated separately, so that a group G which is the Cartesian product of cyclic groups Cpi acts on M. It thus also acts on subsets N of size n. Since the number of elements in G is a power of p, the same is true of any of its orbits. Thus in order to compute \binom{m}{n} modulo p, we only need to consider fixed points of this group action. The fixed points are those subsets N that are a union of some of the cycles. More precisely one can show by induction on k-i, that N must have exactly ni cycles of size pi. Thus the number of choices for N is exactly

\prod_{i=0}^k\binom{m_i}{n_i}\pmod{p}.

Variations and generalizations

References

  1. ^
  2. ^ Andrew Granville (1997). "Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers". Canadian Mathematical Society Conference Proceedings 20: 253–275. MR1483922. http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf. 

External links